{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 练习题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. 实现下列算法，并给出算法的时间复杂度。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 求一个 n 阶方阵的所有元素之和。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：$O(n^2)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def matrixSum(matrix):\n",
    "    sum = 0\n",
    "    for arr in matrix:\n",
    "        for num in arr:\n",
    "            sum += num\n",
    "    return sum\n",
    "\n",
    "matrixSum([[1, 2, 3], [4, 5, 6], [7, 8, 9]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 对于输入的任意三个整数，将他们按从小到大的顺序输出。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "109 908 1000\n"
     ]
    }
   ],
   "source": [
    "def sort(a, b, c):\n",
    "    minNum = a\n",
    "    midNum = a\n",
    "    maxNum = a\n",
    "    if b < minNum:\n",
    "        minNum = b\n",
    "    else:\n",
    "        midNum = b\n",
    "    \n",
    "    if c < minNum:\n",
    "        maxNum = midNum\n",
    "        midNum = minNum\n",
    "        minNum = c\n",
    "    elif c > midNum:\n",
    "        maxNum = c\n",
    "    else:\n",
    "        maxNum = midNum\n",
    "        midNum = c\n",
    "    \n",
    "    print(minNum, midNum, maxNum)\n",
    "    \n",
    "sort(109, 908, 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. 对于输入的任意 n 个整数，输出其中的最大元素和最小元素。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, 0)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def getMaxAndMin(arr):\n",
    "    minNum = arr[0]\n",
    "    maxNum = arr[0]\n",
    "    for i in range(1, len(arr)):\n",
    "        if arr[i] < minNum:\n",
    "            minNum = arr[i]\n",
    "        elif arr[i] > maxNum:\n",
    "            maxNum = arr[i]\n",
    "    \n",
    "    return (maxNum, minNum)\n",
    "            \n",
    "getMaxAndMin([10, 0, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. 设 n 为正整数，给出下列各种算法关于 n 的时间复杂度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(1)\n",
    "```c\n",
    "void fun1(int n)\n",
    "{\n",
    "    int i = 1, k = 100;\n",
    "    while(i < n)\n",
    "    {\n",
    "        k = k + 1;\n",
    "        i += 2:\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A:\n",
    "$i = 2T(n) + 1 \\le n - 1\\\\\n",
    "T(n) \\le \\frac n2 - 1\\\\\n",
    "T(n) = O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(2) \n",
    "```c\n",
    "void fun2(int b[], int n)\n",
    "{\n",
    "    int i, j, k, x;\n",
    "    for (i = 0, i < n - 1, i++)\n",
    "    {\n",
    "        k = i;\n",
    "        for (j = i, j < n, j++)\n",
    "            if (b[k] > b[j]) k = j;\n",
    "        x = b[i]; b[i] = b[k]; b[k] = x;\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A: \n",
    "$T(n) = \\sum\\limits_{i=0}^{n-1}\\sum\\limits_{j=i+1}^{n-1}1\\\\\n",
    "= \\sum\\limits_{i=0}^{n-1}(n-i-1)\\\\\n",
    "= (n-1)^2 - \\sum\\limits_{i=0}^{n-2}\\\\\n",
    "= (n-1)(n-1-\\frac {n-2}{2})\\\\\n",
    "= \\frac {n^2-n}{2}\\\\\n",
    "T(n) = O(n^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(3)\n",
    "```c\n",
    "void fun3(int n)\n",
    "{\n",
    "    int i = 0, s = 0;\n",
    "    while(s < n)\n",
    "    {\n",
    "        i++;\n",
    "        s = s + i;\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A:\n",
    "$s = \\sum\\limits_{i=1}^{T(n)} \\le n-1\\\\\n",
    "\\frac {T(n)(1+T(n))}{2} \\le n-1\\\\\n",
    "T(n) = |\\frac {-1-\\sqrt{8n-7}}{2}| = \\frac {1+\\sqrt{8n-7}}{2}\\\\\n",
    "T(n) = O(\\sqrt{n})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6. 有以下递归算法用于对数组 a[i..j] 的元素进行归并排序：\n",
    "\n",
    "```c\n",
    "void mergesort(int a[], int i, int j)\n",
    "{\n",
    "    int m;\n",
    "    if (i != j)\n",
    "    {\n",
    "        m = (i + j) / 2;\n",
    "        mergesort(a, i, m);\n",
    "        mergesort(a, m + 1, j);\n",
    "        merge(a, i, j, m);\n",
    "    }\n",
    "}\n",
    "```\n",
    "求 mergesort(a, 0, n-1) 的时间复杂度，其中 merge(a, i, j, m) 用于两个有序子序列 a[i..m] 和 a[m+1..j] 的合并，是一个非递归函数，它的时间复杂度为O(合并的元素个数)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A:\n",
    "$T(n) =\n",
    "\\begin{cases}\n",
    "1& \\text{n=1}\\\\\n",
    "2T(\\frac {n}{2})+n& \\text{n>1, 加 n 为 merge 的时间复杂度}\n",
    "\\end{cases}$\n",
    "\n",
    "$T(n) = 2T(\\frac n2) + n\\\\\n",
    "= 2 \\times (2T(\\frac n4) + \\frac n2) + n\\\\\n",
    "= 2 \\times (2 \\times (2T(\\frac n8) + \\frac n4) + \\frac n2) + n\\\\\n",
    "= 2^3T(\\frac n{2^3})+3n\\\\\n",
    "$\n",
    "\n",
    "$\n",
    "T(n) = 2^kT(\\frac n{2^k})+kn\\\\\n",
    "2^k=n 时，T(n)=1\\\\\n",
    "T(n) = n+n\\log_2n\\\\\n",
    "T(n)=O(n\\log_2n)\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 上机实验题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 设计一个程序，输出所有小于等于 n (n 为一个大于2的正整数)的素数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "要求：（1）每行输出10素数；（2）尽可能采用较优的算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**isPrime 时间复杂度**\n",
    "\n",
    "$(2T(n)+1)^2 \\le n\\\\\n",
    "T(n) \\le \\frac {{\\sqrt n}-1}2\\\\\n",
    "T(n) = O(\\sqrt n)\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**时间复杂度**\n",
    "\n",
    "$T(n) = \\frac 12\\sum\\limits_{i=2}^{n}\\sqrt i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3 5 7 11 13 17 19 23 29 \n",
      "\n",
      "31 37 41 43 47 53 59 61 67 71 \n",
      "\n",
      "73 79 83 89 97 101 "
     ]
    }
   ],
   "source": [
    "def getAllPrimeLessThanOrEqualTo(n):\n",
    "    print(2, end=' ')\n",
    "    column = 1\n",
    "    for i in range(3,n+1, 2):\n",
    "        if isPrime(i):\n",
    "            if column == 10:\n",
    "                print('\\n')\n",
    "                column = 0\n",
    "            print(i, sep='\\t', end=' ')\n",
    "            column += 1\n",
    "\n",
    "def isPrime(n):\n",
    "    if n <= 2:\n",
    "        return True\n",
    "    if n % 2 == 0:\n",
    "        return False\n",
    "    cur = 3\n",
    "    while cur <= n / cur:\n",
    "        if n % cur == 0:\n",
    "            return False\n",
    "        cur += 2\n",
    "    return True\n",
    "\n",
    "n = 101\n",
    "# for i in range(2,n+1):\n",
    "#     print(i, isPrime(i))\n",
    "getAllPrimeLessThanOrEqualTo(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 编写一个程序，计算任意输入的各位数字之和。并分析算法的时间复杂度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**时间复杂度**\n",
    "\n",
    "$n \\div 10^{T(n)} \\ge 1\\\\\n",
    "10^{T(n)} \\le n\\\\\n",
    "T(n) \\le \\log_{10}n\\\\\n",
    "T(n) = O(\\log_2n)\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "64"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sumOfNumber(n):\n",
    "    sum = 0\n",
    "    while n >= 1:\n",
    "        sum += n % 10\n",
    "        n = n // 10\n",
    "    return sum\n",
    "\n",
    "sumOfNumbers(1221231231231239899)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. 编写一个程序，判断一个字符串是否为“回文”。并分析算法的时间复杂度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**时间复杂度**\n",
    "\n",
    "$T(n) = \\frac n2\\\\\n",
    "T(n) = O(n)\n",
    "$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abc False\n",
      "aba True\n",
      "acbfg False\n",
      "acbca True\n",
      "abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcba True\n",
      "abcdefghijklmnopqrstuvwxyzyxwvutsrqponmlkjihgfedcba True\n",
      "abcdefghijklmnopqrstuvwxyhzyxwvutsrqponmlkjihgfedcba False\n"
     ]
    }
   ],
   "source": [
    "def isPalindrome(string):\n",
    "    head = 0\n",
    "    peer = len(string) - 1\n",
    "    while head < peer:\n",
    "        if string[head] != string[peer]:\n",
    "            return False\n",
    "        head += 1\n",
    "        peer -= 1\n",
    "    return True\n",
    "\n",
    "strings = ['abc',\n",
    "          'aba',\n",
    "          'acbfg',\n",
    "          'acbca',\n",
    "          'abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcba',\n",
    "          'abcdefghijklmnopqrstuvwxyzyxwvutsrqponmlkjihgfedcba',\n",
    "          'abcdefghijklmnopqrstuvwxyhzyxwvutsrqponmlkjihgfedcba']\n",
    "for string in strings:\n",
    "    print(string, isPalindrome(string))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
